package com.zyk.grate_offer.class12;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author zhangsan
 * @date 2021/6/5 13:44
 */
public class Code05_LongestConsecutive {

    // O(N*logN + N)
    public static int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums);
        int maxLen = 0;
        int pre = nums[0], curLen = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != pre) {
                if (nums[i] - nums[i - 1] == 1) {
                    curLen++;
                } else {
                    maxLen = Math.max(maxLen, curLen);
                    curLen = 1;
                }
                pre = nums[i];
            }
        }
        return Math.max(maxLen, curLen);
    }


    // O(N)
    public static int longestConsecutive2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        HashMap<Integer, Integer> head = new HashMap<>();       // key: num, value: len 以num为开头的最长连续
        HashMap<Integer, Integer> tail = new HashMap<>();       // key: num, value: len 以num结束的最长连续
        int maxLen = 0;
        for (int num : nums) {
            if (head.containsKey(num) || tail.containsKey(num)) continue;
            // node: num, 1
            head.put(num, 1);
            tail.put(num, 1);
            // 有没有以num-1为尾巴的
            if (tail.containsKey(num - 1)) {
                tail.put(num, tail.remove(num - 1) + 1);
            }
            // 有没有以num+1为头的
            if (head.containsKey(num + 1)) {
                head.put(num, head.remove(num + 1) + 1);
            }
            maxLen = Math.max(maxLen, head.get(num) + tail.get(num) - 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
//        int[] nums = {1, 2, 0, 1};
//        int[] nums = {100,4,200,1,3,2};
        int[] nums = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        System.out.println(longestConsecutive(nums));
        System.out.println(longestConsecutive2(nums));

        int times = 10000;
        int maxLen = 1000;
        int maxVal = 500;
        for (int i = 0; i < times; i++) {
            int[] arrs = generateRandomArray(maxLen, maxVal);
            int ans1 = longestConsecutive(arrs);
            int ans2 = longestConsecutive2(arrs);
            System.out.println(ans1 + "\t" + ans2);
            if(ans1 != ans2) {
                System.out.println("OOPS");
                break;
            }
        }
    }

    public static int[] generateRandomArray(int maxLen, int maxVal) {
        maxLen = (int) (Math.random() * (1 + maxLen));
        int[] res = new int[maxLen];
        for (int i = 0; i < res.length; i++) {
            res[i] = (int) (Math.random() * (maxVal >> 1));
        }
        return res;
    }

}
